I created a typical game structure so the game loop is used to initialise, update and render elements. Events and input handling is performed in the main loop. Also the creation of GUI, navigation graph and calling chosen pathfinding algorithm are also placed in Application class.
Path node in my application is a class which holds gCost (distance to Start Node), hCost(distance to End Node), pointer to parent node (previous node) and vector of pointers to all neighbours. Path node can be set as visited or as obstacle. Visited and obstacle nodes will be avoided in neighbour checks. Node is visually represented by rectangle shape (sf::RectangleShape) which can change its size and color.
I decided to create a 2D grid to represent a navigation graph, because it is very easy to connect neighbour nodes as there are maximum 8 directions (including diagonals) where neighbour nodes might be placed. It will be less, if the node is placed on the grid border or one or more neighbours are set as obstacles.
Grid class is responsible for creation of the navigation graph and for updating of the nodes states (drawing obstacles, setting start and end nodes positions, connecting nodes with their neighbours).
I created a Pathfinder class which is responsible for performing path finding calculation and measuring the performance and cost of current algorithm. Currently there are 3 pathfinding algorithms available in my application.
These are:
- A* algorithm
- Dijkstra algorithm
- Breadth-First Search algorithm
A* Algorithm
A* is one of the best techniques used in pathfinding and graph traversals. A* algorithm achieves better performance than Dijkstra or BFS, because it uses heuristics to guide its search. It will scan the area only in direction of the final destination. Astar is mostly used and valuable algorithm if we know both the source point and destination point. In Astar we use both gCost (movement cost from starting point to the current node) and hCost(estimated movement cost to move from the current node to the end node).
I calculate the approximation of heuristic by using Euclidean distance which is calculated like so: hCost = sqrt((CurrentNode.x - target.x)2 + (CurrentNode.y - target.y)2)
We can use this heuristic as we are allowed to move in any directions.
First I reset all the nodes so all nodes become unvisited (if not start/end/obstacle) and the hCost and gCost are set as infinite. Then I create a pointer which will be a pointer to the current node. Initially pointer will point to start node as this is the current node at the start of algorithm. Then I create a list of unvisited nodes.
Initially I used std::list, however I had to sort the list each loop which is a very slow process as the time complexity is logarithmic(O(nlogn)) for list sorting algorithm.
Instead I decided to use a priority queue which will hold not only the pointers to the nodes but the hCost as well. In order to do that I used std::pair and set each pair like so: std::pair which contains float and Node*. So the final pair definition will look as shown below:
The priority queue will store the pairs and will sort the contents based on the first value in pair (float). Using this approach after calling the Top() function we will get the element with the lowest float which in case of A* algorithm will be our hCost.
Dijkstra Algorithm
Dijkstra algorithm is very similar to A*. The biggest difference between these two is that Dijkstra algorithm do not use heuristic (hCost is always 0). It is usually used if we know the source node, but we don't know the position of the target node. Because we are not using heuristic, the cost of the algorithm will be higher due to checks of all the neighbouring nodes.
The implementation of Dijkstra is very similar to A*. I am just not using the hCost of the nodes at all. It means that the pairs are made from 2 values, float(gCost here) and Node*(pointer to current node). The rest of the implementation is almost identical. We also do not have to update the hCost of the visited node. We only update the gCosts.
Breadth-First Search Algorithm
This algorithm also do not use heuristic. It is not using gCost either. BFS will search all the nodes until the target is found. As in previous algorithm each node can be visited only once. Unvisited nodes are added to the queue(std::queue) and then the front elements are retrieved and dequeued. Currently explored neighbour nodes are enqueued into the queue.
At the end of each algorithm the path from the start to end node will be drawn using connection between the nodes. Each node has its parent(previous node) connected to it. Using a while loop all nodes and their parents (starting from the end node) will change the tile color to blue.
GUI consists of simple clickable and not clickable elements. The main element of gui is a menu panel. All added buttons will be positioned and rendered on the top of the panel.
